package BinaryTree;

public class UsePostAndInCreateTree {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int postIndex;

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            postIndex = postorder.length - 1;
            return buildTreeChild(inorder, postorder, 0, inorder.length - 1);
        }

        public TreeNode buildTreeChild(int[] inorder, int[] postorder, int inbegin, int inend) {
            //在这种情况下，表明root，没有子树
            if (inbegin > inend) {
                return null;
            }
            TreeNode root = new TreeNode(postorder[postIndex]);
            int rootIndex = finVal(inorder, inbegin, inend, postorder[postIndex]);
            postIndex--;
            root.right = buildTreeChild(inorder, postorder, rootIndex + 1, inend);
            root.left = buildTreeChild(inorder, postorder, inbegin, rootIndex - 1);
            return root;
        }

        private int finVal(int[] inorder, int inbegin, int inend, int val) {
            for (int i = inbegin; i <= inend; i++) {
                if (inorder[i] == val) {
                    return i;
                }
            }
            return -1;
        }
    }
}
